#include <bits/stdc++.h>
using namespace std;

#define MAXN 10000

struct edge_t
{
   int da, pr, la;
};
struct aux_t
{
   int fa, de, si;
};

struct tree_t
{
#define LG2MAXN 32
   int top;
   //edge_t e[MAXN * 2];
   int da[MAXN * 2], pr[MAXN * 2], la[MAXN * 2];
   aux_t aux[MAXN];
   int anc[MAXN][LG2MAXN + 1];
   tree_t()
   {
      memset(da, 0, sizeof(da));
      memset(pr, 0, sizeof(pr));
      memset(la, 0, sizeof(la));
      memset(aux, 0, sizeof(aux));
      memset(anc, 0, sizeof(anc));
      top = 0;
   }

   void link(int p, int c)
   {
      da[++top] = c;
      pr[top] = la[p];
      la[p] = top;
   }

   void dfs(int p)
   {
      for (int i = la[p]; i; i = pr[i])
         dfs(da[i]);
   }

   void dfs(int x, int fath)
   {
      for (int i = la[x]; i; i = pr[i])
      {
         if (x != fath)
            dfs(da[i], x);
      }
   }

   void CalcAux(int x, int fath)
   {
      aux[x].de = aux[fath].de + 1;
      aux[x].fa = fath;
      anc[x][0] = fath;
      for (int i = 1; i < LG2MAXN; i++)
         anc[x][i] = anc[anc[x][i - 1]][i - 1];

      for (int i = la[x]; i; i = pr[i])
      {
         if (da[i] != fath)
         {
            CalcAux(da[i], x);
            aux[x].si += aux[da[i]].si;
         }
      }
   }

   void view(int n)
   {
      printf("%3s%5s%5s%5s%5s%5s%5s\n", "i", "fa", "de", "si", "da", "pr", "la");

      for (int i = 0; i < n; i++)
      {
         aux_t &ax = aux[i];
         printf("%3d%5d%5d%5d%5d%5d%5d\n", i, ax.fa, ax.de, ax.si, da[i], pr[i], la[i]);
      }
   }

   int LCA_a1(int x, int y)
   {
      while (x != y)
      {
         if (aux[x].de > aux[y].de)
            x = aux[x].fa;
         else
            y = aux[y].fa;
      }
      return x;
   }

   int LCA_MoT(int x, int y)
   {
      if (aux[x].de < aux[y].de)
         swap(x, y);
      int delta = aux[x].de - aux[y].de;
      for (int j = 0; j < LG2MAXN; j++)
         if ((1 << j) & delta)
            x = anc[x][j];
      if (x == y)
         return x;
      for (int j = LG2MAXN; j >= 0; j--)
         if (anc[x][j] != anc[y][j])
            x = anc[x][j], y = anc[y][j];
      return anc[x][0];
   }
};

int main()
{
   tree_t tr;
   // tree_t tr2;
   int x, y, n = 0;
   while (cin >> x >> y)
   {
      n = max(n, x);
      n = max(n, y);
      tr.link(x, y);
      tr.link(y, x);
      // tr2.link(x, y);
      // tr2.link(y, x);
   }
   tr.CalcAux(1, 0);
   tr.view(2 * n);
   // tr2.CalcAux(1, 0);
   // tr2.view(2 * n);
   x = 3, y = 11;
   printf("LCA(%d, %d)=%d (MoT:%d)\n", x, y, tr.LCA_a1(x, y), tr.LCA_MoT(x, y));
   x = 10, y = 11;
   printf("LCA(%d, %d)=%d (MoT:%d)\n", x, y, tr.LCA_a1(x, y), tr.LCA_MoT(x, y));
   x = 8, y = 11;
   printf("LCA(%d, %d)=%d (MoT:%d)\n", x, y, tr.LCA_a1(x, y), tr.LCA_MoT(x, y));
   return 0;
}

/*

      1
      |
      |
   11  2    3  9
   /        \
  /          \
4 5  10    6 7 8

NO ROOT:
11 1
1 2
1 3
11 4
11 5
3 6
3 7
3 8
9 1
11 10



  i   fa   de   si   da   pr   la
  0    0    0    0    0    0    0
  1    0    1    0    1    0   18
  2    1    2    0   11    0    4
  3    1    2    0    2    2   15
  4   11    3    0    1    0    8
  5   11    3    0    3    3   10
  6    3    3    0    1    0   12
  7    3    3    0    4    1   14
  8    3    3    0   11    0   16
  9    1    2    0    5    7   17
 10   11    3    0   11    0   20
 11    1    2    0    6    6   19
 12    0    0    0    3    0    0
 13    0    0    0    7   11    0
 14    0    0    0    3    0    0
 15    0    0    0    8   13    0
 16    0    0    0    3    0    0
 17    0    0    0    1    0    0
 18    0    0    0    9    5    0
 19    0    0    0   10    9    0
 20    0    0    0   11    0    0
 21    0    0    0    0    0    0
LCA(3, 11)=1 (MoT:1)
LCA(10, 11)=11 (MoT:11)
LCA(8, 11)=1 (MoT:1)
*/
